   #include "unionFind.hpp"

bool UnionFind::isLegalId(int id) {
	return (id > 0) && (id <= n);
}

/* We allocate n + 1 sets and members, although we will use only the ones in
indexes 1..n, just for convinience.
*/
UnionFind::UnionFind(int n) : n(n),
sets(new Set[n + 1]),
forest(new Member[n + 1]) {
	for (int i = 1; i <= n; ++i) {
		sets[i] = Set(i);
		forest[i].setSet(i);
	}
}

UnionFind::~UnionFind() {
	delete[] sets;
	delete[] forest;
}

bool UnionFind::isSet(int setId) {
	return sets[setId].doesExist;
}

void UnionFind::unite(int targetSet, int setToUnite) {
	if ((!isLegalId(targetSet)) || (!isLegalId(setToUnite))) {
		throw InvlidIdException();
	}

	if ((!isSet(targetSet)) || (!isSet(setToUnite))) {
		throw InexistentSetException();
	}

	if (targetSet == setToUnite) {
		// There is nothing to be done.
		return;
	}

	/* Determining which of the sets is bigger (in order to unite the small
	set to the big set).
	*/
	int bigSet = INVALID_VALUE;
	int smallSet = INVALID_VALUE;
	if (sets[targetSet].size >= sets[setToUnite].size) {
		bigSet = targetSet;
		smallSet = setToUnite;
	}
	else {
		bigSet = setToUnite;
		smallSet = targetSet;
	}
	int bigMember = sets[bigSet].forestIndex;
	int smallMember = sets[smallSet].forestIndex;

	// Uniting
	forest[smallMember].setParent(bigMember);
	forest[bigMember].setSet(targetSet);

	/* Making targetSet "point to" the bigger set in the forest,
	and the setToUnite "point to" no set (this set ceases exisiting).
	*/
	sets[targetSet].size += sets[setToUnite].size;
	sets[targetSet].forestIndex = bigMember;

	sets[setToUnite].doesExist = false;
}

int UnionFind::find(int memberId) {
	if (!isLegalId(memberId)) {
		throw InvlidIdException();
	}

	// setHeadId will store the index of the head / root member of the set.
	int setHeadId = memberId;
	while (INVALID_VALUE != forest[setHeadId].getParent()) {
		setHeadId = forest[setHeadId].getParent();
	}

	// Shrinking routes
	while (INVALID_VALUE != forest[memberId].getParent()) {
		int parent = forest[memberId].getParent();
		forest[memberId].setParent(setHeadId);
		memberId = parent;
	}

	return forest[setHeadId].getSet();
}